from typing import List


# O(N) 动态规划


class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        size = len(stones)

        # 计算前缀和
        prefix = [0]
        for i in range(size):
            prefix.append(prefix[-1] + stones[i])

        # dp[i] = i前面已经被合成1个球的情况下，i之后能够产生的最大分数之差
        dp = [float("-inf")] * size
        dp[size - 1] = prefix[size]
        for i in range(size - 2, 0, -1):
            dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1])

        return dp[1]


if __name__ == "__main__":
    print(Solution().stoneGameVIII([-1, 2, -3, 4, -5]))  # 5
    print(Solution().stoneGameVIII([7, -6, 5, 10, 5, -2, -6]))  # 13
    print(Solution().stoneGameVIII([-10, -12]))  # -22
